package com.brett.frame.learn.sort.insert;

/**
 * 希尔排序
 * @author lenovo
 *
 */
public class ShellSort {

	public int[] sort(int[] arr) {
		int incr = arr.length;
		do {
			incr = incr / 3 + 1;

			for (int i = incr; i < arr.length; i += incr) {

				if (arr[i - incr] > arr[i]) {
					int tmp = arr[i];// 使用临时变量，减少交换次数
					int j = i - incr;
					for (; j >= 0 && arr[j] > tmp; j -= incr) {
						arr[j + incr] = arr[j];
					}
					arr[j + incr] = tmp;
				}
			}
		} while (incr > 1);
		return arr;
	}
}
